package cn.hy.today;

import java.util.ArrayList;
import java.util.List;

class Solution_2477 {

    long ans = 0;

    public long minimumFuelCost(int[][] roads, int seats) {
        int n = roads.length;
        List[] g = new List[n + 1];
        for (int i = 0; i <= n; i++) {
            g[i] = new ArrayList<Integer>();
        }
        for (int[] e : roads) {
            g[e[0]].add(e[1]);
            g[e[1]].add(e[0]);
        }
        dfs(0, -1, seats, g);
        return ans;
    }

    public int dfs(int cur, int fa, int seats, List<Integer>[] g) {
        int peopleCntSum = 1;
        for (int ne : g[cur]) {
            if (ne != fa) {
                // 计算所有的子节点
                int peopleCnt = dfs(ne, cur, seats, g);
                peopleCntSum += peopleCnt;
                ans += (peopleCnt + seats - 1) / seats;
            }
        }
        return peopleCntSum;
    }

}